package com.atwy.sort;

import java.util.Arrays;

/**
 * 归并排序，是建立在归并操作上的一种有效的排序算法。
 * 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。
 * 代价是需要额外的内存空间。
 * <p>
 * 算法步骤
 * 1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 * 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 * 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 * 4.重复步骤 3 直到某一指针达到序列尾；
 * 5.将另一序列剩下的所有元素直接复制到合并序列尾。
 */
public class MergeSorting {
    public static void main(String[] args) {
        int[] array = {3, 65, 2, 34, 12, 5, 9, 12};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        System.out.println("=============");

        /*int max = 80000;
        int arry[] = new int[max];
        for (int i = 0; i < max; i++) {
            arry[i] = (int)(Math.random()*8000000);
        }
        long start = System.currentTimeMillis();
        System.out.println("排序开始:"+start);
        sort(arry);
        long end = System.currentTimeMillis();
        System.out.println("排序结束:"+end);
        System.out.println("总耗时"+(end-start));*/

    }

    public static void sort(int[] array) {
        int[] ints = divide(array);
        // array = ints;// 这样是没用的，数组不能用引用传递
        for (int i = 0; i < array.length; i++) {
            array[i] = ints[i];
        }
    }

    /**
     * 分
     *
     * @param array
     * @return
     */
    private static int[] divide(int[] array) {
        if (array.length < 2) {
            return array;
        }
        int middle = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, middle);// 包头不包尾
        int[] right = Arrays.copyOfRange(array, middle, array.length);
        // 分 - 治
        return merge(divide(left), divide(right));
    }

    /**
     * 合
     *
     * @param left
     * @param right
     * @return
     */
    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {

            if (i >= left.length) {// 左边已完成
                result[index] = right[j++];
                //j++;
            } else if (j >= right.length) {// 右边已完成
                result[index] = left[i++];
                //i++;
            } else if (left[i] > right[j]) {// 最小的入结果队列中
                result[index] = right[j++];
                //j++;
            } else {
                result[index] = left[i++];
                //i++;
            }
        }

        return result;
    }
}
